package test;

public class Submit3 {
    public static void main(String[] args) {
        int n = 720;
        System.out.println(solution(n));
    }

    public static int solution(int N) {
        String S = Integer.toString(N);
        int[] A = new int[S.length()];
        for (int i = 0; i < S.length(); ++i)
            A[i] = S.charAt(i) - '0';
        if (permutations(A, 0)) {
            return 1;
        } else {
            return 0;
        }
    }
    public static boolean isPowerOfThree(int[] A) {
        if (A[0] == 0) {
            return false;  // no leading zero
        }

        int N = 0;
        for (int x: A) {
            N = 10 * N + x;
        }
        return getRes(N);
    }

    public static boolean permutations(int[] A, int start) {
        if (start == A.length) {
            return isPowerOfThree(A);
        }

        for (int i = start; i < A.length; ++i) {
            swap(A, start, i);
            if (permutations(A, start + 1)) {
                return true;
            }
            swap(A, start, i);
        }

        return false;
    }

    public static void swap(int[] A, int i, int j) {
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
    private static boolean getRes(int num) {
        if (num < 1){
            return false;
        }
        if (num == 1){
            return true;
        }
        if (num % 3 != 0){
            return false;
        } else {
            return getRes(num / 3);
        }
    }

}
